package listbyorder.access001_100.test72;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/4 8:25
 */
public class Solution1 {

    // 方法一： 暴力递归
    public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        return getAns(word1, 0, len1, word2, 0, len2);
    }

    private int getAns(String word1, int s1, int e1, String word2, int s2, int e2) {
        if (s1 == e1) return e2 - s2;
        if (s2 == e2) return e1 - s1;
        if (word1.charAt(s1) == word2.charAt(s2)) {
            return getAns(word1, s1 + 1, e1, word2, s2 + 1, e2);
        } else {
            return 1 + Math.min(
                    Math.min(getAns(word1, s1 + 1, e1, word2, s2, e2), getAns(word1, s1, e1, word2, s2 + 1, e2)),
                    getAns(word1, s1 + 1, e1, word2, s2 + 1, e2));
        }
    }
}
